#include<iostream>
#include<vector>
#include<map>
#include<assert.h>
#include<list>
#include<functional>
#include<thread>
using namespace std;

//struct Point
//{
//	int _x; 
//	int _y;
//
//	//构造函数
//	Point(int x, int y)
//		: _x(x)
//		, _y(y)
//	{}
//};
//
//
//int main()
//{
//	//C++11扩大了用大括号括起的列表(初始化列表)的使用范围，使其可用于所有的内置类型和用户自定义的类型，
//	//使用初始化列表时，可添加等号(=)，也可不添加。
//	
//	// 内置类型变量
//	int c = { 2 };
//	int b{ 2 }; // 赋值符号也可以省略
//	// 数组
//	int arr1[5]{ 1,2,3,4,5 }; // 赋值符号也可以省略
//	// 自定义结构体
//	Point p1{ 1, 2 };
//
//	// *动态数组，在C++98中不支持
//	int* arr3 = new int[5]{ 1,2,3 }; //后两个按数组初始化的特性，会初始化为0
//	
//	Point* ptr = new Point[2]{ { 1, 2 }, { 3, 4 } };//因为沿袭自C语言的特性，该行代码不用写构造函数也可以完成初始化，
//	                                                //但是如果写了构造函数就会进行多参数构造函数的隐式类型转换，此时如果用explicit进行阻止就会编译报错。
//	Point p2{ 3, 4 };//该行代码不用写构造函数也可以完成初始化，因为该特性是沿袭自C语言的。
//					 
//	Point p3(5, 6);//该行没构造函数无法通过编译，这里其实是C++11支持的多参数构造函数的隐式类型转换，可以用explicit阻止。	
//	//总结：最好写一个对应的构造函数
//
//	// 标准容器
//	vector<int> v1 = { 1,2,3,4,5 };
//	vector<int> v2{ 1,2,3,4,5 };
//	map<int, int> m{ {1,1}, {2,2,},{3,3},{4,4} };	
//	//// typeid()的使用
//	//cout << typeid(m).name() << endl;
//	//int x1 = 1;
//	//const int y1 = 2;
//	//cout << typeid(x1).name() << " " << typeid(y1).name() << endl; 
//	////typeid().name()拿到的类型不区分是否为const变量，故此处取到的x与y的类型都是int
//
//	// decltype()的使用
//	int x = 1;
//	double y = 2.2;
//	//用decltype推演x*y的实际类型，作为定义c的类型。
//	decltype(x * y) ret;
//	//推导x的类型，作为定义z的类型。
//	decltype(x) z; 
//	//用decltype推导出来的类型还可以用来做模板参数（这个auto无法替代）
//	vector<decltype(x)> v;
//
//	return 0;
//}
//int fmin(int x, int y)
//{
//	return x > y ? y : x;
//}
//
//int main()
//{
//	//交叉引用:
//	//左值引用能否引用右值？右值引用能否引用左值？
//	
//	int x = 1, y = 2;
//	//常见右值	
//	10;
//	x + y;
//	fmin(x, y);
//
//	//常见左值
//	int* p = new int(0);
//	int b = 1;
//	const int c = 2;
//
//	//左值引用能否引用右值？ --- 不能直接引用，但是const左值引用可以引用右值
//	const int& r1 = 10;
//	const int& r2 = x + y;
//	const int& r3 = fmin(x, y);
//
//	//右值引用能否引用左值？ --- 不能直接引用，但是右值引用可以引用move以后的左值
//	int*&& rr1 = move(p);
//	int&& rr2 = move(*p);
//	int&& rr3 = move(b);
//	const int&& rr4 = move(c);
//
//	//需要注意的是右值是不能取地址的，但是给右值取别名后，会导致右值被存储到特定的位置，且可以取到该位置的地址。
//	//eg:
//	10; //不能取字面常量10的地址
//	int&& rr = 10;
//	int*&& prr = &rr; //rr引用过后可以对rr取地址
//	*prr = 9; //也可以修改rr	
//
//	return 0;
//}

//string
namespace bit
{
	class string
	{
	public:
		typedef char* iterator;
		iterator begin()
		{
			return _str;
		}

		iterator end()
		{ 
			return _str + _size;
		}

		string(const char* str = "")
			:_size(strlen(str))
			, _capacity(_size)
		{
			cout << "string(const char* str)" << endl;

			_str = new char[_capacity + 1];
			strcpy(_str, str);
		}

		// s1.swap(s2)
		void swap(string& s)
		{
			::swap(_str, s._str);
			::swap(_size, s._size);
			::swap(_capacity, s._capacity);
		}

		// 拷贝构造
		string(const string& s) // 参数是一个左值
			:_str(nullptr)
			, _size(0)
			, _capacity(0)
		{
			cout << "string(const string& s) ---> 深拷贝" << endl;

			string tmp(s._str);
			swap(tmp);
		}

		// 移动构造
		string(string&& s) // 参数是一个右值（用参数区别调用的是移动构造还是拷贝构造）
			:_str(nullptr) // 要将自己的_str置为空
			, _size(0)
			, _capacity(0)
		{
			cout << "string(string&& s) ---> 资源转移" << endl;

			this->swap(s);
		}

		// 赋值重载
		string& operator=(const string& s)
		{
			cout << "string& operator=(const string& s) ---> 深拷贝" << endl;
			string tmp(s);
			swap(tmp);

			return *this;
		}

		//移动赋值
		string& operator=(string&& s)
		{
			cout << "string& operator=(const string&& s) ---> 转移资源" << endl;
			swap(s);

			return *this;
		}

		string& operator+=(char ch)
		{
			push_back(ch);
			return *this;
		}

		string operator+(char ch)
		{
			string tmp(*this);
			tmp.push_back(ch);

			return tmp; // 返回的tmp是一个将亡值
		}

		~string()
		{
			delete[] _str;
			_str = nullptr;
		}

		char& operator[](size_t pos)
		{
			assert(pos < _size);
			return _str[pos];
		}

		void reserve(size_t n)
		{
			if (n > _capacity)
			{
				char* tmp = new char[n + 1];
				strcpy(tmp, _str);
				delete[] _str;
				_str = tmp;

				_capacity = n;
			}
		}

		void push_back(char ch)
		{
			if (_size >= _capacity)
			{
				size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;
				reserve(newcapacity);
			}

			_str[_size] = ch;
			++_size;
			_str[_size] = '\0';
		}

		const char* c_str() const
		{
			return _str;
		}
	private:
		char* _str; // 底层就是一个char*的指针，指向new出来的一块空间
		size_t _size;
		size_t _capacity; // 不包含最后做标识的'\0'
	};

	bit::string to_string(int value)
	{
		bit::string str;
		while (value)
		{
			int val = value % 10;
			str += ('0' + val);
			value /= 10;
		}
		reverse(str.begin(), str.end());

		return str;
	}

}

//// 场景1
//// 左值引用做参数，基本完美的解决所有问题
//void func1(bit::string s)//传值传参，一次深拷贝
//{}
//
//void func2(const bit::string& s)//传引用传参，防止了深拷贝，且左值右值都可以接收
//{}
//
// 场景2
// 左值引用做返回值，只能解决部分问题
// string& operator+=(char ch) 解决了（出了作用域对象还在的情况，可以传引用返回）
// string operator+(char ch)   没有解决（出了作用域对象不在的情况，只能传值返回）
//
// 右值引用，如何解决operator+传值返回存在拷贝的问题呢？---> 提供了移动构造，可以把纯右值、将亡值的资源转移
// C++11 将右值分为：纯右值，将亡值
//纯右值：内置类型。eg；10、x + y、fmin(x, y)
//将亡值：自定义类型、自定义类型的临时对象，匿名对象。

//// 场景3
//// 提供了移动构造，右值引用可以完美解决场景2解决不了的问题
//bit::string func3()
//{
//	bit::string str("hello world");
//
//	return str; // str为将亡值，会调用移动构造
//}
//
//int main()
//{
//	//bit::string str("hello world");
//	//func1(str);
//	//func2(str);
//	//func3();
//
//	//bit::string s("1111111111111111111111111111");
//	//bit::string s1 = s;
//	// 
//	//bit::string s2 = move(s);
//
//	//bit::string s1("hello world");
//	//bit::string s2("xxxxx");
//	//s1 = s2;
//
//	// 临时对象 和 优化后的str都会被编译器置为右值
//	bit::string ret = bit::to_string(1234); // 本来是str先拷贝构造给临时对象，临时对象再拷贝给ret
//	                                        // 有移动构造后：str先拷贝构造给临时对象，临时对象移动构造转移资源给ret
//	                                        // 再加上编辑器优化：str直接移动构造给ret
//	bit::string ret1;
//	ret1 = bit::to_string(1234);            // 本来是str先拷贝构造给临时对象，然后调用赋值操作符重载（里面会深拷贝），完成赋值
//	                                        // 有移动构造、string& operator=(string&& s)后：
//	                                        // str先移动构造转移资源给临时对象，然后调用&&版赋值操作符重载（直接交换资源），完成赋值
//									
//	return 0;
//}
//////////////////////////////////////////////////////////////////////////////////////
//
//int main()
//{
//	list<bit::string> lt;
//	bit::string s("111111");
//	lt.push_back(s); //插入一个左值，调用void push_back(const _Ty& _Val)，拷贝构造
//	cout << endl;
//
//	lt.push_back("222222"); // 先调用单参数构造函数，构造一个临时对象（这个临时对象是将亡值），
//							//再调用void push_back(_Ty&& _Val)，移动构造
//	cout << endl;
//
//	lt.push_back(bit::to_string(333333)); // 先调用to_string函数，该函数内部创造了一个string类对象，
//	                                      // 传值返回时会调用一次移动构造构造一个临时对象做返回值，
//	                                      //再调用void push_back(_Ty&& _Val)，移动构造*2
//	cout << endl;
//}
//
//void Fun(int& x) { cout << "左值引用" << endl; }
//void Fun(const int& x) { cout << "const 左值引用" << endl; }
//
//void Fun(int&& x) { cout << "右值引用" << endl; }
//void Fun(const int&& x) { cout << "const 右值引用" << endl; }
//
//// 模板中的&&不代表右值引用，而是万能引用，其既能接收左值又能接收右值。
//// 但是引用类型后续使用中都会退化成左值，如果要保持住引用类型的右值属性，就要用到forward关键字
//template<typename T>
//void PerfectForward(T&& t)
//{
//	Fun(t); // t退化成了左值
//	Fun(std::forward<T>(t)); // C++用forward关键字来保持住参数t的右值属性
//	cout << "----------------" << endl;
//}
//
//int main()
//{
//	PerfectForward(10);           // 右值
//
//	int a;
//	PerfectForward(a);            // 左值
//	PerfectForward(std::move(a)); // 右值
//
//	const int b = 8;
//	PerfectForward(b);		      // const 左值
//	PerfectForward(std::move(b)); // const 右值
//
//	return 0;
//}

//list
template<class T>
struct ListNode
{
	ListNode* _next = nullptr;
	ListNode* _prev = nullptr;
	T _data;
};
template<class T>
class List
{
	typedef ListNode<T> Node;
public:
	List()
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
	}

	void PushBack(T&& x)
	{
		// 只要是右值引用，再传递其他函数调用，要保持右值属性，必须用完美转发
		Insert(_head, std::forward<T>(x));
	}

	void Insert(Node* pos, T&& x)
	{
		Node* prev = pos->_prev;
		////法一：
		//Node* newnode = new Node;
		//newnode->_data = std::forward<T>(x); //这里会调用类型T的移动赋值

		//法二：
		Node* newnode = (Node*)malloc(sizeof(Node));
		new(&newnode->_data)T(std::forward<T>(x));  //用定位new初始化_data，这里会调用类型T的移动构造
		// prev newnode pos
		prev->_next = newnode;
		newnode->_prev = prev;
		newnode->_next = pos;
		pos->_prev = newnode;
	}

	void Insert(Node* pos, const T& x)
	{
		Node* prev = pos->_prev;
		Node* newnode = new Node;
		newnode->_data = x; 

		// prev newnode pos
		prev->_next = newnode;
		newnode->_prev = prev;
		newnode->_next = pos;
		pos->_prev = newnode;
	}
private:
	Node* _head;
};

//int main()
//{
//	List<bit::string> lt;
//	lt.PushBack("1111");
//	lt.PushBack("2222");
//
//	return 0;
//}
//
//int main()
//{
//	vector<Goods> v = { { "苹果", 2.1, 5 }, { "香蕉", 3, 4 }, { "橙子", 2.2, 3 }, { "菠萝", 1.5, 4 } };
//	sort(v.begin(), v.end(), ComparePriceLess());
//	sort(v.begin(), v.end(), ComparePriceGreater());
//}
//
//int main()
//{
//	// 实现一个两个数相加的lambda
//	auto add1 = [](int a, int b)->int{return a + b; }; // lambda表达式没有名字，
//													   // 所以只能用auto推导其类型 												   // decltype也能推导其类型，但一般不这样用 eg: decltype(add1) fun;
//	cout << add1(1, 2) << endl;													   												   
//	// 返回值类型可以省略
//	auto add1 = [](int a, int b){return a + b; };
//	cout << add1(1, 2) << endl; 
//	// 没有参数可以省略参数列表
//	auto func1 = []{cout << "hello world" << endl; };
//	func1(); // 使用时还是要加上()
//
//	return 0;
//}
//
//int main()
//{	
//	int d = 1;
//	auto f1 = [d] { d; };
//	//auto f2 = [d] { d++; }; //会报错，不能在非可变lambda中修改按值捕获，
//	//                        //因为d是const的，若要修改，需用mutable取消其常量性	
//	auto f3 = [d]()mutable { d++; }; //使用mutable时，参数列表不可省略（即使参数为空）
//	auto f4 = [&d] { d++; };//能在非可变lambda中修改按值引用捕获
//
//	int a = 1, b = 2;
//
//	//正常写法
//	auto swap1 = [](int& x, int& y) {
//		int z = x;
//		x = y;
//		y = z;
//	};
//
//	swap1(a, b);
//
//	//使用捕捉列表写法
//	auto swap2 = [a, b]()mutable { //传值捕捉，并不会改变函数外部的a、b 
//		int z = a;
//		a = b;
//		b = z;
//	};
//
//	swap2();
//
//	auto swap3 = [&a, &b](){ //传引用捕捉，会改变函数外部的a、b
//		int z = a;
//		a = b;
//		b = z;
//	};
//
//	swap3();
//
//	//打印lambda表达式的类型：
//	cout << typeid(swap3).name() << endl;
//	
//	return 0;
//}
//
//
//
//class A
//{
//public:
//	// 写了带参构造之后编辑器就不会生成默认构造了
//	A(int a) 
//		: _a(a)
//	{}
//	// 显式指定编译器生成默认构造
//	A() = default;
//	// 防拷贝：禁止编译器生成默认的拷贝构造函数以及赋值运算符重载
//	A(const A&) = delete;
//	A& operator=(const A&) = delete;
//private:
//	int _a = 0;
//};
//
//
//int main()
//{
//	int d = 1;
//	auto f1 = [d] { d; };
//	//auto f2 = [d] { d++; }; //会报错，不能在非可变lambda中修改按值捕获，
//	//                        //因为d是const的，若要修改，需用mutable取消其常量性	
//	auto f3 = [d]()mutable { d++; }; //使用mutable时，参数列表不可省略（即使参数为空）
//	auto f4 = [&d] { d++; };//能在非可变lambda中修改按值引用捕获
//
//	auto f5 = [](int x, int y) {x++; y++; }; //传值，不会影响外部的值
//	auto f6 = [](int& x, int& y) {x++; y++; }; //传引用，会影响外部的值
//
//	int x = 0, y = 0;
//	f5(x, y); //x、y值不会改变
//	f6(x, y); //x、y值会改变
//
//	return 0;
//}
//
//
//template <class ...Args>
//void Count(Args... args)
//{
//	//计算参数包中参数的个数：
//	cout << sizeof...(Args) << endl; 
//	cout << sizeof...(args) << endl;
//}
//
//// 递归终止函数
//template <class T>
//void ShowList(const T& t)
//{
//	cout << t << endl << endl;
//}
//
//// 解析并打印参数包中每个参数的类型及值
//template <class T, class ...Args>
//void ShowList(T val, Args... args)// val解析出第一个参数，剩下的参数放入args
//{
//	cout << typeid(val).name() << ":" << val << endl;
//	ShowList(args...);// 递归解析args，当只剩下一个参数时，调递归终止函数
//}
//
//template <class T>
//void PrintArg(T val)
//{
//	T copy(val);
//	cout << typeid(T).name() << ":" << val << endl;
//}
//
////展开函数
//template <class ...Args>
//void ShowList(Args... args)
//{
//
//	int arr[] = { (PrintArg(args), 0)... };
//	
//	int arr[] = { (PrintArg(args), 0), (PrintArg(args), 0), (PrintArg(args), 0), (PrintArg(args), 0) ...};
//
//
//	cout << endl;
//}
//
//
//int main()
//{
//	ShowList(1);
//	ShowList(1, 'A');
//	ShowList(1, 'A', std::string("sort"));
//
//	return 0;
//}
//
//template <class T>
//int PrintArg(T val)
//{
//	T copy(val);
//	cout << typeid(T).name() << ":" << val << endl;
//
//	return 0;
//}
//
////展开函数
//template <class ...Args>
//void ShowList(Args... args)
//{
//	int arr[] = { PrintArg(args)... }; //arr未给大小，要开多少空间取决于{}中的值的个数
//	cout << endl;
//}
//
//int main()
//{
//	// push_back与emplace_back的区别（使用上）
//	std::list< std::pair<int, char> > mylist;
//	mylist.push_back(make_pair(1, 'A'));
//	mylist.push_back({ 1, 'A' }); //C++11支持自定义类型用列表初始化
//	mylist.emplace_back(make_pair(1, 'A'));
//	mylist.emplace_back(1, 'A'); //emplace版本的优势，emplace_back支持可变参数，拿到pair对象的参数后自己去创建对象。
//	//mylist.emplace_back({ 1, 'A' }); error 不支持
//	
//	// push_back与emplace_back的区别（底层）
//	// push_back是构造+移动构造；emplace_back是直接构造
//	std::list< std::pair<int, bit::string> > mylist_1;
//	mylist_1.emplace_back(10, "sort");
//	mylist_1.emplace_back(make_pair(20, "sort"));
//	cout << endl << endl;
//	mylist_1.push_back(make_pair(30, "sort"));
//	mylist_1.push_back({ 40, "sort" });
//
//	return 0;
//
//}
//
//
//using namespace std;
//class testDemo
//{
//public:
//	testDemo(int num) :num(num) {
//		std::cout << "调用构造函数" << endl;
//	}
//	testDemo(const testDemo& other) :num(other.num) {
//		std::cout << "调用拷贝构造函数" << endl;
//	}
//	testDemo(testDemo&& other) :num(other.num) {
//		std::cout << "调用移动构造函数" << endl;
//	}
//private:
//	int num;
//};
//
//int main()
//{
//	testDemo t1(2);
//	cout << "emplace_back:" << endl;
//	std::vector<testDemo> demo1;
//	demo1.emplace_back(t1);
//	//demo1.emplace_back(move(t1));  
//
//	cout << "push_back:" << endl;
//	std::vector<testDemo> demo2;
//	demo2.push_back(t1);
//	//demo1.push_back(move(t1));  
//}
//
//template<class F, class T> // 定义一个函数模板
//T useF(F f, T x) // f可能是函数指针，可能是仿函数，可能是lambda
//{
//	static int count = 0;
//	cout << "count:" << ++count << endl;
//	cout << "count:" << &count << endl;
//
//	return f(x);
//}
//
//double f(double i)
//{
//	return i / 2;
//}
//
//struct Functor
//{
//	double operator()(double d)
//	{
//		return d / 3;
//	}
//};
//
//int main()
//{
//	// 情况一、函数名
//	cout << useF(f, 11.11) << endl;
//	// 情况二、函数对象
//	cout << useF(Functor(), 11.11) << endl;
//	// 情况三、lambda表达式
//	cout << useF([](double d)->double { return d / 4; }, 11.11) << endl;
//
//	// 效率太低了，因为像情况一、二、三useF函数模板被实例化成了三份（因为F被推导成了）
//
//	// 如何只实例化出一份呢？---包装器
//
//
//	return 0;
//}

//int f(int a, int b)
//{
//	return a + b;
//}
//
//struct Functor
//{
//public:
//	int operator() (int a, int b)
//	{
//		return a * b;
//	}
//};
//
//class Plus
//{
//public:
//	static int plusi(int a, int b)
//	{
//		return a + b + 1;
//	}
//	double plusd(double a, double b)
//	{
//		return a + b;
//	}
//};
//
//int main()
//{
//	//包装函数指针
//	function<int(int, int)> f1 = f;
//	cout << f1(1, 2) << endl;
//
//	//包装仿函数
//	function<int(int, int)> f2 = Functor();
//	cout << f2(1, 2) << endl;
//
//	//包装静态成员函数
//	function<int(int, int)> f3 = &Plus::plusi;
//	cout << f3(1, 2) << endl;
//
//	//包装非静态成员函数
//	function<double(Plus, double, double)> f4 = &Plus::plusd;
//	cout << f4(Plus(), 1.1, 2.2) << endl;
//
//	//包装器把不同的可调用对象类型包装成了统一的类型
//
//	return 0;
//}
//
//int SubFunc(int a, int b)
//{
//	return a - b;
//}
//
//class Sub
//{
//public:
//	int sub(int a, int b)
//	{
//		return a - b;
//	}
//};
//
//int main()
//{
//	function<int(int, int)> f1 = SubFunc;
//	cout << f1(10, 3) << endl;
//
//	function<int(int, int)> f2 = bind(SubFunc, placeholders::_1, placeholders::_2);
//	cout << f2(10, 3) << endl;
//
//	// 通过bind调整参数顺序
//	function<int(int, int)> f3 = bind(SubFunc, placeholders::_2, placeholders::_1);
//	cout << f3(10, 3) << endl;
//
//	// 通过bind调整参数个数
//	function<int(Sub, int, int)> f4 = &Sub::sub;
//	cout << f4(Sub(), 10, 3) << endl;
//
//	function<int(int, int)> f5 = bind(&Sub::sub, Sub(), placeholders::_1, placeholders::_2);
//	cout << f5(10, 3) << endl;
//	
//	auto f6 = bind(&Sub::sub, Sub(), placeholders::_1, placeholders::_2);
//	cout << f6(10, 3) << endl;
//
//	return 0;
//}

//static int x = 0;
//
//void Func(int n)
//{
//	for (int i = 0; i < n; ++i)
//	{
//		++x;
//	}
//}
//
//int main()
//{
//	thread t1(Func, 5000000);
//	thread t2(Func, 5000000);
//	//让主线程等待
//	t1.join();
//	t2.join();
//
//	cout << x << endl;
//
//	return 0;
//}

//// 原子操作的++
//
//atomic<int> x = 0;
//void Func(int n)
//{
//	for (int i = 0; i < n; ++i)
//	{
//		++x; //该++操作是原子的
//	}
//}
//
//int main()
//{
//	thread t1(Func, 5000000);
//	thread t2(Func, 5000000);
//	t1.join();
//	t2.join();
//
//	cout << x << endl;
//	return 0;
//}

//void func(int& X)
//{
//	cout << "X:" << &X << endl;
//	X++;
//}
//
////实现对x的++
//int main()
//{
//	int x = 0;
//	cout << "x:" << &x << endl;
//	////严格来说thread可执行函数参数不能是左值引用
//	//thread t1(func, x); //--->vs2019会报错,vs2013不会报错但n不会被修改（是13支持C++11的bug）
//	//t1.join();
//
//	//解决方案一、 ---> 用传地址的方式
//	//解决方案二、
//	thread t1(func, std::ref(x));
//	t1.join();
//
//	cout << x << endl;
//	return 0;
//}




